package hot100;


/*
 * Author：江松
 * Date：2023/4/12 10:35
 *
 比特位计数:
 1,移位 O(nlogN)
 2，内置函数 O(n)
 */

public class Main338 {
    public int[] countBits(int n) {
        int res[]=new int[n+1];
        res[0]=0;
        for(int i=1;i<=n;++i){
            int t=i;
            while(t!=0){
                res[i]+=t&1;
                t>>=1;
            }
        }
        return res;
    }
    /*
    //内置函数O(n)
    public int[] countBits(int n) {
        int res[]=new int[n+1];
        res[0]=0;
        for(int i=1;i<=n;++i){
            res[i]=Integer.bitCount(i);
        }
        return res;
    }
    */
}
